package zuoshen.chapter4;

public class FibonacciSequence {

    //递归
    public static int fl(int n){
        if(n == 0){
            return 0;
        }
        if(n == 1 || n==2){
            return 1;
        }
        return fl(n-1) + fl(n-2);
    }

    //备忘数组记录
    public static int arrFl(int n){
        if(n==0){
            return 0;
        }
        int[] arr = new int[n+1];
        arr[0] = 0;
        arr[1] = 1;
        arr[2] = 1;
        return arrFl(n,arr);
    }

    public static int arrFl(int n , int[] arr){
        if(arr[n] > 0){
            return arr[n];
        }
        arr[n] = arrFl(n-1,arr) + arrFl(n-2,arr);
        return arr[n];
    }

    //动态规划
    public static int dymamicProgramFl(int n){

        if(n==0){
            return 0;
        }
        if(n==1 || n==2){
            return 1;
        }

        int a = 0;
        int b = 1;
        int res = 0;
        for(int i = 2 ; i <= n;i++){
            res = a + b;
            a = b;
            b = res;
        }
        return res;

    }


    public static void main(String[] args) {
        System.out.println(fl(15) == arrFl(15));
        System.out.println(fl(10) == dymamicProgramFl(10));
    }

}
